#include<iostream>
#include<algorithm>
using namespace std;

enum Colour
{
  RED,
  BLACK
};

template<class K, class V>
struct RBTreeNode
{
  pair<K, V> _kv;
  RBTreeNode<K, V>* _left;
  RBTreeNode<K, V>* _right;
  RBTreeNode<K, V>* _parent;

  Colour _col;

  RBTreeNode(const pair<K, V>& kv)
    :_kv(kv)
     , _left(nullptr)
     , _right(nullptr)
     , _parent(nullptr)
  {}
};

template<class K, class V>
class RBTree
{
  typedef RBTreeNode<K, V> Node;
public:
  bool Insert(const pair<K, V>& kv)
  {
    if(_root == nullptr)
    {
      _root = new Node(kv);
      _root->_col - BLACK;
      return true;
    }
    
    Node* parent = nullptr;
    Node* cur = _root;
    while(cur)
    {
      if(cur->_kv.flist < kv.first)
      {
        parent = cur;
        cur = cur->_right;
      }
      else if(cur->_kv.first > kv.first)
      {
        parent = cur;
        cur = cur->_left;
      }
      else{
        return false;
      }
    }
    cur = new Node(kv);
    cur->_col = RED;
    if(parent->_kv.first < kv.first)
    {
      parent->_right = cur;
    }
    else{
      parent->_left = cur;
    }
    cur->_parent = parent;
    while(parent && parent->_col == RED)
    {
      Node* grandfather = parent->_parent;
      if(grandfather->_left == parent)
      {
        Node* uncle = grandfather->_right;
        if(uncle && uncle->_col == RED)
        {
          //变色
          parent->_col = uncle->_col = BLACK;
          grandfather->_col = RED;

          //继续向上处理
          cur = grandfather;
          parent = cur->_parent;
        }
        else//uncle不存在，或者存在且为黑
        {

        }
      }
    }
  }

private:
  Node* _root = nullptr;
};

